Corelab Seminar
2010-2011
Spyridon Antonakopoulos
(Bell labs)
Approximating Directed Buy-at-bulk Network Design
Abstract.
Buy-at-bulk network design is a well-known problem that has been researched extensively on undirected graphs.
In this paper, we initiate the theoretical study of the same problem on directed graphs, thus capturing real-life situations
where the cost of installing capacity on an edge is asymmetric with respect to direction, as e.g. in the design of wireless and satellite
communication networks.
More specifically, we develop two approximation algorithms for directed buy-at-bulk network design in the non-uniform
cost model. Combined, they achieve a ratio of O(min(k^(1/2 + epsilon), n^(4/5 +epsilon)) for any constant epsilon > 0, where n is the number
of nodes of the network and k is the number of demand pairs to be connected. Further, the above ratio is independent of the amount of traffic
flowrequested by each demand pair, which may vary arbitrarily, and it canbe remarkably improved when all demand pairs share a common sink
(or a common source, symmetrically).
To the best of our knowledge, this is the first non-trivial approximation factor established for the
aforementioned problem, and naturally it also applies to more restricted cost models, such as the uniform and rent-or-buy models. Moreover, it
essentially matches the best currently known approximation guarantees for directed Steiner forest, which may be viewed as a special case of directed
buy-at-bulk network design.